package leetcode.all;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution22 {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    public static List<String> generateParenthesis(int n) {
        ArrayList<ArrayList<String>> records = new ArrayList<>();
        //set iter base n=0 string=""
        records.add(new ArrayList<>(Arrays.asList(new String[]{""})));
        for (int i = 1; i <= n; i++) {
            ArrayList<String> curRecord = new ArrayList<>();
            for (int j = 0; j <= i-1 ; j++) {
                //concat (records[j]),records[i-1-j], 0<=j<=i-1
                for (String p: records.get(j)) {
                    for (String q: records.get(i-1-j)) {
                        curRecord.add("("+p+")"+q);
                    }
                }
            }
            records.add(curRecord);
        }
        return (List)records.get(n);
    }
}
